package problem238;


//238.除自身以外数组的乘积
//https://leetcode.cn/problems/product-of-array-except-self/

class Solution {
    public int[] productExceptSelf(int[] nums) {
        int n = nums.length;
        int[] sub1 = new int[n+1];
        int[] sub2 = new int[n+1];
        sub1[0] = sub2[n] = 1;
        for(int i = 1; i<=n; i++) {
            sub1[i] = sub1[i-1] * nums[i-1];
        }
        for(int i = n-1; i>=0; i--) {
            sub2[i] = sub2[i+1] * nums[i];
        }
        int[] ret = new int[n];
        for(int i = 0; i<n; i++) {
            ret[i] = sub1[i] * sub2[i+1];
        }
        return ret;
    }
}

/*

sub1[i]: 数组0~i-1之间元素的乘积
sub2[i]: 数组i~n-1之间元素的乘积

1 2 3 4
1 1 2 6 24
25 24 12 4  1
*/